The present invention relates to digital imaging.
When working with digital images, it is frequently necessary to transform an image from one color space to a second color space; for example, from an RGB (Red Green Blue) color space to a CMYK (Cyan Magenta Yellow blacK) color space. Many methods used for color conversion use a lookup table that is organized as an n-dimensional lattice, with n representing the number of input color channels. In order to determine output values for input values that are between two entries in the look-up table, some sort of interpolation technique is desirable.
In such a table, 2n adjacent lattice points form an n-dimensional cube around a provided input value, for which an output value is desired. To facilitate computation, most methods transform the input values so that 0 in all channels maps to the vertex of the cube with the lowest values in all input channels (which will be referred to as the starting point), and 1 in all channels maps to the vertex with the highest values in all input channels (which will be referred to as the end point). A method commonly known as linear interpolation uses all 2n adjacent lattice points to calculate an output value. However, this method is quite slow, as the number of terms that must be calculated is m×2′, where m is the number of output channels.
In hedral methods, the cube is subdivided into n! subvolumes, known as hedra, each with n+1 vertices. For example, six tetrahedra are used for three input channels, and 24 hedra are used for four input channels. The starting point, the end point, and the line between these two points (the diagonal of the cube) are shared by all hedra. The hedron that encloses the input point is used to calculate the output value. Because only n+1 vertices are used, the output value can be obtained by only calculating n+1 terms, which is much faster than using the linear interpolation method.